//
//  ProblemOffer53-2.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/15.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 53 - II. 0～n-1中缺失的数字 ✅
 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 示例 1:
     输入: [0,1,3]
     输出: 2
 示例 2:
     输入: [0,1,2,3,4,5,6,7,9]
     输出: 8
 限制：1 <= 数组长度 <= 10000
 */
@objcMembers class ProblemOffer53_2: NSObject {
    func solution() {
        print(missingNumber([0]))
        print(missingNumber([1]))
        print(missingNumber([1,2]))
        print(missingNumber([0,1,2]))
        print(missingNumber([0,1,3]))
        print(missingNumber([0,1,2,3,4,5,6,7,9]))
    }
    
    /*
     二分法
     */
    func missingNumber(_ nums: [Int]) -> Int {
        return missingNumberE(nums, 0, nums.count-1)!
    }
    
    func missingNumberE(_ nums: [Int], _ s: Int, _ e: Int) -> Int? {
        if s == e {
            return nums[s] == s ? s+1 :  s
        }
        
        let mid = (e + s) / 2
        return mid == nums[mid] ? missingNumberE(nums, mid+1, e) : missingNumberE(nums, s, mid)
    }
}
